上一章節我們為了解決BST有可能成為spindly tree的議題，介紹了可以永遠保持balance的B-Tree；但其實有一種更直覺的方式就可以讓BST變得balance，那就是rotate。

以下是把G往左轉的說明，rotateLeft的定義就是讓自己成為原本右側小孩的左側小孩：

同理，rotateRight就是讓自己成為原本左側小孩的右側小孩：

所以可以想像，藉由多次的rotate操作是可以把BST變得balance的～只是就是要找出那個algorithm，但目前還沒有人研究出來（或許就是未來的你！）

雖然還沒找到可以rotate成balance tree的演算法，但是已經有人想出了很妙的妙招！

我們知道B-Tree一定是balance的，有沒有可能把B-Tree用另一種方式呈現成BST呢？這種呈現方式就稱為Red Black Tree：

可以看到，像AC、EJ、SX在2-3 tree中是3 node(也就是一個node底下可以有3個child node)，藉由把鏈結標記成紅色，就可以轉譯成一般的BST！

因為這邊選擇左邊的鏈結為紅色，所以就稱為LLRB(Left-Leaning Red Black BST)。

紅黑樹主要有兩個特點：

1. 從根節點到最遠的子節點，其黑鍵數量就等於轉譯為B-Tree時的高度(height)，因為B-Tree一定是balance的，亦即所有leaf node到root node距離都一樣。
2. 不會有連續兩個紅鍵，因為這代表會違背2-3 tree每個node塞2個元素，node最多3個小孩的型態。

接下來的問題就是，該如何去建構紅黑樹呢？比較好的做法會是先按照一般的BST法則來加node，然後在一些特定的情況時進行rotate來達到跟2-3 tree一樣的型態，也就是加紅鍵。

第一個步驟就是，當我們加元素時，是要建立紅鍵還是黑鍵？答案會是紅鍵，因為在2-3 tree中，我們會優先把元素塞進node中直到滿出來，所以為了去達到LLRB一對一2-3 tree的結果，會建立紅鍵。

但如果都優先建立紅鍵，就會發生以下問題：

說好的LLRB勒～怎麼會有紅鍵在右側！

這時就可以應用到一開始介紹的rotate了～

我們把右側紅鍵的情況，藉由rotateLeft(E)，就可以把紅鍵轉到左邊了！

再來是如果遇到塞滿2-3 tree的node的情形，這時候是暫時的，因為2-3 tree的規則會再把塞滿的node的元素往上丟。這時候該如何表示呢？

就會變成一個node左右兩側都是紅鍵，但這種情況也不會是最終型態，我們接著看下去。

這時候就是奇蹟的時刻，我們可以發現temporary 4 node(代表該node可以有4個child node)在2-3 tree轉換後的最終型態，我們只要把左右兩邊的紅鍵往上一層丟，就搞定了！這個動作稱為flip(B)。

以下是Red Black Tree的建構規則總結：

由於紅黑樹可以完全的轉譯成2-3 tree，所以add跟contains的runtime也會是O(logN)。

目前介紹了三種search tree，他們都是潛在實作Map跟Set的選擇；不過除了tree型態的解法，其實一開始介紹的LinkedList也是可以透過特殊的方法達到有效率的實作(Skip List)。除此之外，還有一種也很常見的實作方法，會在下一章節介紹～

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License